#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int minCut(string s) {
    int n = s.size();
    vector<vector<bool>> IsPath(n, vector<bool>(n));
    vector<int> dp(n, INT_MAX);
    dp[0] = 0;

    for (int i = n - 1; i >= 0; --i)
        for (int j = i; j < n; ++j)
            if (s[i] == s[j])
                IsPath[i][j] = i + 1 >= j ? true : IsPath[i + 1][j - 1];

    for (int i = 1; i < n; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            if (IsPath[0][i])
                dp[i] = 0;
            if (IsPath[j][i])
                dp[i] = min(dp[i], dp[j - 1] + 1);
        }
    }

    return dp[n - 1];
}

int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = n - 1; i >= 0; --i)
    {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; ++j)
        {
            if (s[i] == s[j])
                dp[i][j] = dp[i + 1][j - 1] + 2;
            else
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
        }
    }

    return dp[0][n - 1];
}

int main()
{
    minCut("aab");
	return 0;
}